「杂题记录」「NOI 2018」屠龙勇士

📄 PDF 📝 Source

小 D 最近在网上发现了一款小游戏。游戏的规则如下:

  • 游戏的目标是按照编号 1n1 \rightarrow n 顺序杀掉 nn 条巨龙,每条巨龙拥有一个初始的生命值 aia_i 。同时每条巨龙拥有恢复能力,当其使用恢复能力时,它的生命值就会每次增加 pip_i ,直至生命值非负。只有在攻击结束后且当生命值 恰好00 时它才会死去。
  • 游戏开始时玩家拥有 mm 把攻击力已知的剑,每次面对巨龙时,玩家只能选择一把剑,当杀死巨龙后这把剑就会消失,但作为奖励,玩家会获得全新的一把剑。

小 D 觉得这款游戏十分无聊,但最快通关的玩家可以获得 ION2018 的参赛资格,于是小 D 决定写一个笨笨的机器人帮她通关这款游戏,她写的机器人遵循以下规则:

  • 每次面对巨龙时,机器人会选择当前拥有的,攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑,则选择 攻击力最低 的一把剑作为武器。
  • 机器人面对每条巨龙,它都会使用上一步中选择的剑攻击巨龙固定的 xx 次,使巨龙的生命值减少 x×ATKx \times ATK
  • 之后,巨龙会不断使用恢复能力,每次恢复 pip_i 生命值。若在使用恢复能力前或某一次恢复后其生命值为 00 ,则巨龙死亡,玩家通过本关。

那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性,她想考考你,你知道应该将机器人的攻击次数 xx 设置为多少,才能用最少的攻击次数通关游戏吗?

当然如果无论设置成多少都无法通关游戏,输出 1-1.

测试点编号 nn mm pip_i aia_i 攻击力 其他限制
1 105\le 10^5 =1=1 =1=1 105\le 10^5 =1=1
2 105\le 10^5 =1=1 =1=1 105\le 10^5 =1=1
3 105\le 10^5 =1=1 =1=1 105\le 10^5 105\le 10^5
4 105\le 10^5 =1=1 =1=1 105\le 10^5 105\le 10^5
5 103\le 10^3 103\le 10^3 105\le 10^5 105\le 10^5 105\le 10^5 特性 1、特性 2
6 103\le 10^3 103\le 10^3 105\le 10^5 105\le 10^5 105\le 10^5 特性 1、特性 2
7 103\le 10^3 103\le 10^3 105\le 10^5 105\le 10^5 105\le 10^5 特性 1、特性 2
8 =1=1 =1=1 108\le 10^8 108\le 10^8 106\le 10^6 特性 1
9 =1=1 =1=1 108\le 10^8 108\le 10^8 106\le 10^6 特性 1
10 =1=1 =1=1 108\le 10^8 108\le 10^8 106\le 10^6 特性 1
11 =1=1 =1=1 108\le 10^8 108\le 10^8 106\le 10^6 特性 1
12 =1=1 =1=1 108\le 10^8 108\le 10^8 106\le 10^6 特性 1
13 =1=1 =1=1 108\le 10^8 108\le 10^8 106\le 10^6 特性 1
14 =105=10^5 =105=10^5 =1=1 108\le 10^8 106\le 10^6 无特殊限制
15 =105=10^5 =105=10^5 =1=1 108\le 10^8 106\le 10^6 无特殊限制
16 105\le 10^5 105\le 10^5 所有 pip_i 是质数 1012\le 10^{12} 106\le 10^6 特性 1
17 105\le 10^5 105\le 10^5 所有 pip_i 是质数 1012\le 10^{12} 106\le 10^6 特性 1
18 105\le 10^5 105\le 10^5 无特殊限制 1012\le 10^{12} 106\le 10^6 特性 1
19 105\le 10^5 105\le 10^5 无特殊限制 1012\le 10^{12} 106\le 10^6 特性 1
20 105\le 10^5 105\le 10^5 无特殊限制 1012\le 10^{12} 106\le 10^6 特性 1

特性 1 是指:对于任意的 iiaipia_i \le p_i

特性 2 是指:lcm(pi)106\operatorname{lcm}(p_i) \le 10^6,即所有 pip_i最小公倍数 不大于 10610^6

对于所有的测试点,T5T \le 5,所有武器的攻击力 106\le 10^6,所有 pip_i 的最小公倍数 1012\le 10^{12}

保证 $ T, n, m $ 均为正整数。

分析

易知这可以直接转化为 exCRT 问题。

主要记录一下不定方程的获取所有解问题。

不定方程形如: ax+by=c ax+by=c 其中 x,yx, y 为未知数, a,ba, b 为常数。

裴蜀定理 指出:以上方程有整数解的充要条件为 (a,b)c(a, b)|c

扩展欧几里得 可以解出形如: ax+by=(a,b) ax+by=(a, b) 不定方程的一组整数解。

考虑构造以下式子: a(x+b(a,b))+b(ya(a,b))=(a,b) a\left(x+\frac{b}{(a, b)}\right)+b\left(y-\frac{a}{(a, b)}\right)=(a, b) 不难发现如果令: x=x+b(a,b),y=ya(a,b)x' = x+\frac{b}{(a, b)}, y'=y-\frac{a}{(a, b)},这样构造出来的所有解 x,yx', y' 都能成为不定方程的一组解,可以证明这样的构造方式的调整系数是最小的,能够取到所有解。(个人喜欢把 (a,b)\frac{*}{(a, b)} 称为调整系数

考虑到上面的 扩展欧几里得 解出的方程常数项等于 (a,b)(a, b),而不是 cc ,考虑将解和 (a,b)(a, b) 一同乘 c(a,b)\frac{c}{(a, b)} 即可。

需要注意,乘完 c(a,b)\frac{c}{(a, b)} 后,调整系数 不变

关于题目,也没有题解里面说的那么卡…注意一下数据范围里面 Pi=1P_i = 1 的情况即可。

关于代码,换了一种 exCRT 的写法,应该会好背很多,。